package com.lfg.leetcode.leetcode0;


import java.util.*;

public class No39CombinationSum {

    public static void main(String[] args) {
        List<List<Integer>> ret = combinationSum(new int[]{2, 3, 7}, 18);
        System.out.println(ret);
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> set = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        combinationSum(candidates, new ArrayList<Integer>(), 0, target, set, 0);
        return new ArrayList<>(set);
    }

    public static void combinationSum(int[] candidates, List<Integer> list, int total, int target, List<List<Integer>> set, int index) {
        if (total > target) {
            return;
        } else if (total == target) {
            ArrayList<Integer> l = new ArrayList<>(list);
            Collections.sort(l);
            set.add(l);
        }
        for (int i = index; i < candidates.length; i++) {
            list.add(candidates[i]);
            combinationSum(candidates, list, total + candidates[i], target, set, i);
            list.remove(list.size() - 1);
        }
    }


    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        Map<Integer, Set<List<Integer>>> tmp = new HashMap<Integer, Set<List<Integer>>>();
        int min = Integer.MAX_VALUE;
        for (int i : candidates) {
            min = Math.min(i, min);
            if (i == target) {
                List<Integer> data = new ArrayList<>();
                data.add(i);
                set.add(data);
            } else if (i > target) {
                continue;
            }
            for (int j : candidates) {
                if (i >= target) {
                    continue;
                }
                int total = i + j;
                if (total > target) {
                    continue;
                }
                List<Integer> data = new ArrayList<>();
                data.add(i);
                data.add(j);
                Collections.sort(data);
                if (total == target) {
                    set.add(data);
                } else {
                    Set<List<Integer>> s = tmp.getOrDefault(total, new HashSet<List<Integer>>());
                    s.add(data);
                    tmp.put(total, s);
                }
            }
        }
        int n = target / min;
        while (n > 0) {
            n--;
            Map<Integer, Set<List<Integer>>> map = new HashMap<Integer, Set<List<Integer>>>();
            for (int i : candidates) {
                if (i >= target) {
                    continue;
                }
                for (Map.Entry<Integer, Set<List<Integer>>> entry : tmp.entrySet()) {
                    int total = entry.getKey() + i;
                    if (total > target) {
                        Set<List<Integer>> s = map.getOrDefault(entry.getKey(), new HashSet<List<Integer>>());
                        s.addAll(entry.getValue());
                        map.put(entry.getKey(), s);
                        continue;
                    }
                    Set<List<Integer>> value = entry.getValue();
                    Set<List<Integer>> list = new HashSet<List<Integer>>();
                    for (List<Integer> l : value) {
                        List<Integer> newL = new ArrayList<Integer>(l);
                        newL.add(i);
                        Collections.sort(newL);
                        if (total == target) {
                            set.add(newL);
                        } else {
                            list.add(newL);
                        }
                    }
                    if (list.size() > 0) {
                        Set<List<Integer>> s = map.getOrDefault(total, new HashSet<List<Integer>>());
                        s.addAll(list);
                        map.put(total, s);
                    }
                }
            }
            tmp = map;
        }
        return new ArrayList<>(set);
    }
}

